package com.demo.java.OD401_450.OD443;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【田忌赛马(C&D卷-200分)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146326524
 */
public class OdMain {
    public static void main(String[] args) {
        // 创建 Scanner 对象来从控制台读取输入
        Scanner scanner = new Scanner(System.in);

        // 读入两个数组 a 和 b，分别表示田忌的马和敌人的马的速度
        // 假设输入格式为：每行输入一个数组，数组元素用空格隔开
        int[] a = Arrays.stream(scanner.nextLine().split("\\s+")).mapToInt(Integer::parseInt).toArray();  // 读取田忌的马的速度
        int[] b = Arrays.stream(scanner.nextLine().split("\\s+")).mapToInt(Integer::parseInt).toArray();  // 读取敌人的马的速度

        // 调用函数来计算所有的最优数组组合，并输出结果
        List<int[]> optimalArrays = countOptimalArrays(a, b);

        // 输出最优的排列组合的个数
        System.out.println(optimalArrays.size());

        // 输出每个最优排列组合
        for (int[] arr : optimalArrays) {
            // 打印数组并去掉方括号和逗号
            System.out.println(Arrays.toString(arr).replaceAll("[\\[\\],]", ""));
        }
    }

    /**
     * 计算并返回所有最优的马匹排列组合
     *
     * @param a 田忌的马的速度数组
     * @param b 敌人的马的速度数组
     * @return 最优排列组合的列表
     */
    public static List<int[]> countOptimalArrays(int[] a, int[] b) {
        // 创建一个列表，用于存储所有符合条件的最优排列组合
        List<int[]> optimalArrays = new ArrayList<>();

        // 调用排列组合函数来生成所有的排列，并检查每一个排列是否满足条件
        permute(a, 0, optimalArrays, b);

        return optimalArrays;
    }

    /**
     * 递归生成所有排列组合，并检查每一个排列是否符合条件
     *
     * @param a             田忌的马的速度数组
     * @param start         当前排列的起始位置
     * @param optimalArrays 存储符合条件的排列组合
     * @param b             敌人的马的速度数组
     */
    private static void permute(int[] a, int start, List<int[]> optimalArrays, int[] b) {
        // 当递归到数组的末尾时，表示已经生成了一个排列
        if (start == a.length - 1) {
            // 检查当前排列是否符合条件
            if (isValid(a, b)) {
                // 如果符合条件，则将当前排列加入到最优组合列表中
                optimalArrays.add(Arrays.copyOf(a, a.length));
            }
        } else {
            // 否则，进行递归排列
            // 遍历数组的每个元素，并与当前位置的元素交换
            for (int i = start; i < a.length; i++) {
                swap(a, start, i);  // 交换当前位置元素与i位置元素
                permute(a, start + 1, optimalArrays, b);  // 递归调用排列函数，生成下一个位置的排列
                swap(a, start, i);  // 恢复原数组状态，进行下一个排列的生成
            }
        }
    }

    /**
     * 检查给定的排列是否符合田忌赛马的条件
     * 也就是田忌的马是否能战胜敌人的马
     *
     * @param a 田忌的马的速度数组
     * @param b 敌人的马的速度数组
     * @return 如果当前排列符合条件，则返回true，否则返回false
     */
    private static boolean isValid(int[] a, int[] b) {
        // 遍历每一匹马，检查田忌的马是否能战胜敌人的马
        for (int i = 0; i < b.length; i++) {
            if (a[i] <= b[i]) {  // 如果田忌的马速度不大于敌人的马，则不符合条件
                return false;
            }
        }
        return true;  // 如果所有马都符合条件，则返回true
    }

    /**
     * 交换数组中的两个元素
     *
     * @param arr 数组
     * @param i   第一个元素的索引
     * @param j   第二个元素的索引
     */
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];  // 临时存储第i个元素
        arr[i] = arr[j];     // 将第j个元素赋值给第i个位置
        arr[j] = temp;       // 将临时存储的元素赋值给第j个位置
    }
}
